#include "stdafx.h"


const int N=10000;

void Connect1_1(FILE *fin, FILE *fout){
	int p, q, ids[N];
	int i, t;
	for ( i=0; i<N; ++i ){
		ids[i]=i;
	}
	while ( fscanf(fin, "%d %d", &p, &q)==2 ){
		if ( ids[p]!=ids[q] ){
			for ( t=ids[q], i=0; i<N; ++i ){
				if ( ids[i]==t ){
					ids[i]=t;
				}
			}
		} /*else {
			fprintf(fout, "%d - %d\n", p, q);
		}*/
	}
	return;
}

void Connect1_2(FILE *fin, FILE *fout){
	int p, q, ids[N];
	int i, j;
	for ( i=0; i<N; ++i ){
		ids[i]=i;
	}

	while ( fscanf(fin, "%d %d", &p, &q)==2 ){
		for ( i=p; i!=ids[i]; i=ids[i] );
		for ( j=q; j!=ids[j]; j=ids[j] );

		if ( i!=j ){
			ids[i]=j;
			//fprintf(fout, "%d  %d\n", p, q);
		} else {
			//fprintf(fout,"%d - %d\n", p, q);
		}
		//fprintf(fout,"\n");
	}
	return;
}

void Connect1_3(FILE *fin, FILE *fout){
	int p, q, ids[N];
	int i, j;
	for ( i=0; i<N; ++i ){
		ids[i]=i;
	}

	while ( fscanf(fin, "%d %d", &p, &q)==2 ){
		for ( i=p; i!=ids[i]; i=ids[i] );
		for ( j=q; j!=ids[j]; j=ids[j] );

		if ( i!=j ){
			ids[i]=j;
			//fprintf(fout, "%d  %d\n", p, q);
		} else {
			//fprintf(fout,"%d - %d\n", p, q);
		}
		//fprintf(fout,"\n");
	}
	return;
}

void Connect1_4(FILE *fin, FILE *fout){
	int p, q, ids[N];
	int i, j;
	for ( i=0; i<N; ++i ){
		ids[i]=i;
	}

	while ( fscanf(fin, "%d %d", &p, &q)==2 ){
		for ( i=p; i!=ids[i]; i=ids[i] )
			ids[i]=ids[ids[i]];
		for ( j=q; j!=ids[j]; j=ids[j] )
			ids[j]=ids[ids[j]];
		if ( i!=j ){
			ids[i]=j;
			//fprintf(fout, "%d  %d\n", p, q);
		} else {
			//fprintf(fout,"%d - %d\n", p, q);
		}
		//fprintf(fout,"\n");
	}
	return;
}

void Chapter1_test(){
	FILE *fp=fopen("data.txt", "w");
	const int N=1000;
	const int M=100000;
	int p, q;
	srand(time(NULL));
	for ( int i=0; i<M; ++i ){
		p=rand()%N;
		while ( (q=rand()%N)==p);
		fprintf(fp, "%d %d\n", p, q);
	}
	//fclose(fp);
	//fp=fopen("data.txt", "r");
	freopen( "data.txt", "r", fp );
	monotools::CStopWatch sw;

	sw.Start();
	Connect1_1(fp, stdout);
	printf("1_1 time cost:%f\n", sw.NowInMicroF());

	fseek(fp, 0, SEEK_SET);
	sw.Start();
	Connect1_2(fp, stdout);
	printf("1_2 time cost:%f\n", sw.NowInMicroF());

	fseek(fp, 0, SEEK_SET);
	sw.Start();
	Connect1_3(fp, stdout);
	printf("1_3 time cost:%f\n", sw.NowInMicroF());

	fseek(fp, 0, SEEK_SET);
	sw.Start();
	Connect1_4(fp, stdout);
	printf("1_4 time cost:%f\n", sw.NowInMicroF());

	return;
}